# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=12
    
    PROBLEM
    The following iterative sequence is defined for the set of positive
    integers:

    n → n/2 (n is even)
    n → 3n + 1 (n is odd)

    Using the rule above and starting with 13, we generate the following
    sequence:
    
    13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

    It can be seen that this sequence (starting at 13 and finishing at 1)
    contains 10 terms. Although it has not been proved yet (Collatz Problem),
    it is thought that all starting numbers finish at 1.

    Which starting number, under one million, produces the longest chain?

    NOTE: Once the chain starts the terms are allowed to go above one million.

    
    NOTES
    
    
    REFERENCES
    
    
    PERFORMANCE
    <function get_chain at 0x7f267290b938> reached 51425 in 2.00 sec
    <function get_chain_recursive at 0x7f267290b9b0> reached 20691 in 2.00 sec
    <function get_chain_memoized at 0x7f267290ba28> reached 18608 in 2.00 sec
    time <function solution get_max_chain>: 50.990206 s
"""
#
# Import
#
import time


#
# Globals / Constants
#
def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f s" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected):
    assert value == expected, "value %s != expected %s" % (
        value, expected)


#
# Test Case / Solution
#
@timeit    
def test_case():
    functions = [
        get_chain,
        get_chain_recursive,
        get_chain_memoized
    ]
    number = 13
    expected = [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
    
    for f in functions:
        chain = f(number)
        assert_match(chain, expected)  

    print "test case passed!"

@timeit
def solution():
    return get_max_chain(1000000)
        

#
# Support Code
#
def get_max_chain(limit):
    max_chain = []
    
    for n in xrange(2,limit):
        chain = get_chain(n)
        
        if len(chain) > len(max_chain):
            max_chain = chain
        
        #if n % 10000 == 0: print "at", n
            
    return max_chain


def get_chain(n):
    chain = [n]
    
    while n != 1:
        if n % 2 == 0:
            n = n / 2
        else:
            n = 3*n + 1
            
        chain += [n]
        
    return chain


def get_chain_recursive(chain):
    if type(chain) == int:
        return get_chain_recursive([chain])
    
    last = chain[-1]
        
    if last == 1:
        return chain
    elif last % 2 == 0:
        return get_chain_recursive(chain + [last / 2])
    else:
        return get_chain_recursive(chain + [3*last + 1])
        
        
def get_chain_memoized(chain):
    """using get_chain_memoized.memo as static var; see
    http://stackoverflow.com/a/279586/1093087"""
    if type(chain) == int:
        return get_chain_memoized([chain])
    
    last = chain[-1]
        
    if last == 1:
        get_chain_memoized.memo[chain[0]] = chain[1:]
        return chain
    elif last in get_chain_memoized.memo:
        return chain + get_chain_memoized.memo[last]
    elif last % 2 == 0:
        return get_chain_memoized(chain + [last / 2])
    else:
        return get_chain_memoized(chain + [3*last + 1])
get_chain_memoized.memo = dict()    # static var
    

#
# Additional Tests
#
def test_get_chain_performance():
    functions = [
        get_chain,
        get_chain_recursive,
        get_chain_memoized
    ]
    
    def time_f(f):
        limit, n, s, t0 = 2, 1, 0, time.time()
        
        while s < limit:
            n += 1
            f(n)
            s = time.time() - t0
            
        return n, s
        
    for f in functions:
        n, s = time_f(f)
        print "%s reached %d in %1.2f sec" % (f, n, s)



#
# Main
#
if __name__ == '__main__':
    test_get_chain_performance()
    test_case()
    print solution()
    